#include <stdio.h>
#include <malloc.h>

//用链表来实现一个队列
/*
 * 链表带头结点，front指针指向头结点 队列为空的条件就是front==rear
 * */
typedef int ElementType;
typedef struct node{
    ElementType data;
    struct node *next;
} Node;

typedef struct queue{
    //两个指针，分别指向头尾结点
    Node *front;//指向链表的头结点
    Node *rear;//指向链表的最后一个结点

} LinkedQueue;

//2.操作
//2.1 创建空队列
/*
 * 函数名：createQueue()
 * 输入:无
 * 输出：队列
 * */
LinkedQueue *createQueue(){
    LinkedQueue *queue=malloc(sizeof(LinkedQueue));//创建分配空间
    //对两个指针赋值
    queue->front= malloc(sizeof(Node));
    queue->front->next=NULL;
    queue->rear=queue->front;
    return queue;

}
//2.2 插入
/*
 * 函数名Enqueue()
 * 输入 队列 元素
 * 输出 int
 * */
int Enqueue(LinkedQueue *queue,ElementType data){
   // 1.新元素---》放到新结点
    Node *newNode= malloc(sizeof (Node));
    newNode->data=data;
    newNode->next=NULL;
    //2.原先链表末尾的结点指向新的结点
    queue->rear->next=newNode;
    //3.rear/Tail指针再指向新的末尾结点（新结点）
    queue->rear=newNode;
    return 1;
}
//2.3 删除
/*
 * 函数名：DeQueue()
 * 输入：队列
 * 输出：被删除的元素
 *
 * */
ElementType Dequeue(LinkedQueue *queue){
    //1.队列为空
    if(queue->front==queue->rear){
        printf("队列为空，无法删除\n");
        return 0;//0代表删除不成功
    }
    //2.队列不为空
    //head/front 指针指向第一个结点的下一个结点
    Node *tmp=queue->front->next;
    ElementType data=tmp->data;
    queue->front->next=tmp->next;
    //2.如果只有一个结点，执行删除会影响rear的指向
    if(tmp->next==NULL){
        queue->rear=queue->front;
    }
    //释放原来第一个结点的空间
    free(tmp);
    return data;//返回被删除的元素
}
int main() {
    //1.创建空队列
    LinkedQueue *queue=createQueue();
    //2.插入
    ElementType data;
    for(int i=0;i<5;i++){
        scanf("%d",&data);
        Enqueue(queue,data);
    }
    //3.删除
    Dequeue(queue);
    Dequeue(queue);
   // printf("Hello, World!\n");
    return 0;
}
